# for i in range(1,10):
#     for j in range(1,i+1):
#         print("{}*{}={}".format(j,i,i*j),end=" ")
#     print()      九九乘法表

# T=int(input())
# i=0
# ls1=[]
# ls2=[]
# while i <= T-1:
#   a,b=map(int,input().split())
#   for n in range(max(a, b), a * b + 1):
#     if n%a==0 and n%b==0:
#         ls1.append(n)
#         ls2.append(i)
#         i+=1
# for i in range(T):
#   print(f'case #{ls2[i]}:\n{ls1[i]}')   最小公倍数 超时

# T=int(input())
# i=0
# ls1=[]
# ls2=[]
# while i <= T-1:
#   import math
#   a,b=map(int,input().split())
#   gcd=math.gcd(a,b)
#   sum=a*b
#   n=sum//gcd
#   ls1.append(n)
#   ls2.append(i)
#   i+=1
# for i in range(T):
#   print(f'case #{ls2[i]}:\n{ls1[i]}')  103 最小公倍数

# T=int(input())
# i=0
# ls1=[]
# ls2=[]
# while i <= T-1:
#     s=0
#     n=int(input())
#     ls1=list(map(int,input().split()))
#     i+=1
#     for m in ls1:
#        if m<=10:
#         s+=1
#     ls2.append(s)
# for a in ls2:
#     print(a)   种麦子


# ls=list(map(int,input().split()))
# ls.sort()
# for i in range(len(ls)):
#     print(ls[i],end=' ')  单行输入




# ls1 = []
# ls2 = []
# for i in range(3):
#     ls=list(map(int,input().split()))
#     ls1.append(ls)
# for i in range(3):
#     ls=list(map(int,input().split()))
#     ls2.append(ls)
# for i in range(2):
#       print(ls1[i][0]+ls2[i][0],ls1[i][1]+ls2[i][1],ls1[i][2]+ls2[i][2],"")
# print(ls1[2][0]+ls2[2][0],ls1[2][1]+ls2[2][1],ls1[2][2]+ls2[2][2])   矩阵和


# T=int(input())
# s=''
# for i in range(T):
#     f='True'
#     ls1=list(map(int,input().split()))
#     if ls1[0]<0:
#         f='False'
#     N=abs(ls1[0])
#     R=ls1[1]
#     while True:
#         mod=N%R
#         N=N//R
#         if mod>=10 :
#            mod = chr(65 + (mod - 10))
#         s=str(mod)+s
#         if N==0:
#           break
#     if f =='False':
#         print(f'-{s}')
#         s=''
#     else:
#         print(s)
#         s=''          进制转换

# T=int(input())
# ls1=[]
# for i in range(T):
#     a,b=map(int,input().split())
#     k=0
#     for n in range(10**(a-1)+b,10**a):
#         if n % 3==0 and (n-b)%10==0:
#             k+=1
#     ls1.append(k)
# for y in range(T):
#     print(f'case #{y}:\n{ls1[y]}')   三的倍数

# ls=list(map(int,input().split()))
# ls.reverse()
# for i in range(len(ls)):
#     print(ls[i],end=' ')   逆序

# n=int(input())
# ls=list(map(int,input().split()))
# ls.sort()
# for i in ls:
#   print(i,end=' ')   冒泡排序


# n=int(input())
# dic={}
# ls1=[]
# for i in range(n):
#   a,b=input().split()
#   a=int(a)
#   dic.__setitem__(a,b)
#   ls1.append(a)
# ls1.sort()
# for i in ls1:
#   print(i,dic[i])    学生信息


# def number_or_chars(x):
#     if x.isdigit():
#         return int(x)
#     else:
#         return x
#
# def find_person_highest(info,kecheng,mark):
#     max = 0
#     max_id = 0
#     index = 0
#     person = []
#     for each in info:
#         if max < each[mark]:
#             max = each[mark]
#             max_id = index
#         index += 1
#     person.append(info[max_id][0])
#     person.append(info[max_id][kecheng])
#     person.append(str(info[max_id][mark]))
#     return person
#
#
# if __name__=="__main__":
#     n=int(input().strip())
#     info=[]
#     for i in range(n):
#         data=list(map(number_or_chars,input().strip().split()))
#         info.append(data)
#
#     print(" ".join(find_person_highest(info,2,3)))
#     print(" ".join(find_person_highest(info,4,5)))
#     print(" ".join(find_person_highest(info,6,7)))      课代表


# n=int(input())
# if 90<=n<=100:
#     print("A")
# elif 80<=n<90:
#     print("B")
# elif 60<=n<80:
#     print("C")
# else:
#     print("D")    分级


# n=float(input())
# pi=3.14
# c=2*pi*n
# s=pi*(n**2)
# print(c)
# print(s)      圆的设计


# h=float(input())
# w=float(input())
# w1=h-100
# w2=(w-w1)/w1
# if w2>0.05or w2<-0.05:
#     print("ill health")
# else:
#     print("Health")     BMI


# T=int(input())
# dic={'-':-1,'0':0,'1':1}
# for i in range(T):
#     ls=list(input())
#     s=0
#     for j in range(len(ls)):
#        s=s+(3**(len(ls)-j-1))*dic[ls[j]]
#     print(f'case #{i}:\n{s}')       平衡三进制


# dic={0:0,1:1,2:1}
# def tbnq(n):
#     if n == 0:
#        return 0
#     elif n == 1 or n == 2:
#        return 1
#     else:
#         if n - 1 in dic:
#             dic[n-1]=dic[n-1]
#         else:
#             dic[n - 1] = tbnq(n - 1)
#         if n - 2 in dic:
#             dic[n - 2] = dic[n - 2]
#         else:
#             dic[n - 2] = tbnq(n - 2)
#         if n - 3 in dic:
#             dic[n - 3] = dic[n - 3]
#         else:
#             dic[n - 3] = tbnq(n - 3)
#         return dic[n - 1] + dic[n - 2] + dic[n - 3]
# T=int(input())
# for i in range(T):
#     n=int(input())
#     print(f'case #{i}:\n{tbnq(n)}')      泰波那契


# p,q,r = list(map(int,input().split()))
# p1,q1,r1=0,0,0
# dic = {1:3,2:1,3:2}
# for i in range(100):
#     if p1 == q1 == r1:
#         ma=max(p,q,r)
#         if ma == p:
#             print(dic[1])
#             r1+=1
#         if ma ==q:
#             print(dic[2])
#             p1+=1
#         if ma ==r:
#             print(dic[3])
#             q1+=1
#     elif p1 == q1 and p1>r1:
#         ma =max(p,r)
#         if ma == p:
#             print(dic[1])
#             r1+=1
#         if ma ==r:
#             print(dic[3])
#             q1+=1
#     elif p1 == r1 and p1 >q1:
#         ma = max(q,r)
#         if ma == q:
#             print(dic[2])
#             p1+=1
#         if ma ==r:
#             print(dic[3])
#             q1+=1
#     elif q1 == r1 and q1 >p1:
#         ma = max(q,p)
#         if ma ==q:
#             print(dic[2])
#             p1+=1
#         if ma ==p:
#             print(dic[1])
#             r1+=1
#     else:
#         ma = max(p1,q1,r1)
#         if ma == p1:
#             print(2)
#             q1+=1
#         elif ma == q1:
#             print(3)
#             r1+=1
#         else:
#             print(1)
#             p1+=1

# a,b,c=map(int,input().split())
# if a+b>c>a-b and a+c>b>a-c and b+c>a>b-c:
#     print("YES")
# else:
#     print("No")    判断是否为三角形

# for i in range(1,101):
#     print(i)         输出1-100

# old=input()
# oushu=[]
# jishu=[]
# for i in range(0,len(old)):
#     if i % 2 ==0:
#         oushu.append(old[i])
#     else:
#         jishu.append(old[i])
# oushu.extend(jishu)
# for s in oushu:
#     print(s,end='')        提取偶数和奇数重新排列

# s=input()
# sum=0
# for i in s:
#     if '0'<=i<='9':
#         sum+=1
# print(sum)  #统计数字个数

# a=input()
# b=a[::-1]
# if a==b:
#     print("Yes")
# else:
#     print("No")   #判断回文

# n=input()
# if n =="Mon":
#     print("Monday")
# elif n=="Tue":
#     print("Tuesday")
# elif n=="Wed":
#     print("Wednesday")
# elif n=="Thu":
#     print("Thursday")
# elif n=="Fri":
#     print("Friday")
# elif n=="Sat":
#     print("Saturday")
# elif n=="Sun":
#     print("Sunday")   #输入星期

# x,y=map(int,input().split())
# print(y,x)   两数交换

# sum=0
# n=int(input())
# i=1
# while i <= n:
#     sum=sum+(((-1)**(i+1))*(1/(i*(i+1))))
#     i+=1
# result='{:.2f}'.format(sum)
# print(result)   n的求和

# a,b=map(int,input().split())
# for i in range(max(a,b),a*b+1):
#     if i%a==0 and i%b==0:
#         print(i)
#         break    最小公倍数

# s=input()
# dic={}
# for i in s:
#     i=i.lower()
#     if i not in dic:
#         dic[i]=1
#     else:
#         dic[i]+=1
# px=sorted(dic)
# for i in px:
#     print(f'{i}:{dic[i]}')  统计字母个数

# if __name__=="__main__":
#     while True:
#         try:
#             n=int(input())
#             if n==0:
#                 break
#             if n==1 or n==2 or n==3:
#                 print(1)
#             if n>=4:
#                 t1,t2,t3=1,1,1
#                 index=4
#                 while index <n+1:
#                     t4=t3+t1
#                     t1=t2
#                     t2=t3
#                     t3=t4
#                     index+=1
#                 print(t4)
#         except EOFError:
#             break        细胞分裂
































